package com.interview.javabase.algorithm.链表;

public class 相交链表 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(4);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(2);
        listNode1.next.next.next.next = new ListNode(5);
        listNode1.next.next.next.next.next = new ListNode(2);
        ListNode partition = partition(listNode1, 3);
        while (partition != null) {
            System.out.println(partition.val);
            partition = partition.next;
        }
    }

    private static ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode temp = head;

        ListNode smallTemp = small;
        ListNode bigTemp = big;

        while (temp != null) {
            if (temp.val < x) {
                smallTemp.next = temp;
                smallTemp = temp;
            } else {
                bigTemp.next = temp;
                bigTemp = temp;
            }

            temp = temp.next;

        }

        smallTemp.next = big.next;
        bigTemp.next = null;
        return small.next;
    }
}
